package likou.tanxin;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/15 16:49
 */
public class _955 {

    public static void main(String[] args) {
        System.out.println(minDeletionSize(new String[]{"abx", "agz", "bgc", "bfc"}));
    }


    public static int minDeletionSize(String[] A) {
        if (A.length < 2) {
            return 0;
        }
        if (A[0].length() == 0) {
            return 0;
        }
        List<String> list = new ArrayList<>();
        Collections.addAll(list, A);
        List<List<String>> xiangtong = new ArrayList<>();
        xiangtong.add(list);
        return digui(xiangtong, 0, 0);
    }

    public static int digui(List<List<String>> A, int i, int daan) {
        if (A.size() == 0 || i == A.get(0).get(0).length()) {
            return daan;
        }
        //存储连续的相同的String
        List<List<String>> xiangtong = new ArrayList<>();
        for (int w = 0;w<A.size();w++){
            List<String> nowS = A.get(w);
            for (int j = 0; j < nowS.size() - 1; j++) {
                if (nowS.get(j).charAt(i) > nowS.get(j + 1).charAt(i)) {
                    return digui(A, i + 1, daan + 1);
                } else if (nowS.get(j).charAt(i) == nowS.get(j + 1).charAt(i)) {
                    List<String> list = new ArrayList<>();
                    //如果开头就大了，就不用比，用map存储！！！
                    char c = nowS.get(j).charAt(i);
                    list.add(nowS.get(j));
                    list.add(nowS.get(j + 1));
                    j++;
                    while (j<nowS.size()-1&&nowS.get(j+1).charAt(i)==c){
                        list.add(nowS.get(j + 1));
                        j++;
                    }
                    j--;
                    xiangtong.add(list);
                }
            }
        }
        return digui(xiangtong, i + 1, daan);
    }
}
